home *** CD-ROM | disk | FTP | other *** search
/ Chip 2005 August (Alt) / CHIP 2005-08.1.iso / program / guvenlik / syslinux-3.07.exe / com32 / lib / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  2004-11-17  |  781 b   |  43 lines
  1. /*
  2.  * qsort.c
  3.  *
  4.  * This is actually combsort.  It's an O(n log n) algorithm with
  5.  * simplicity/small code size being its main virtue.
  6.  */
  7.  
  8. #include <stddef.h>
  9. #include <string.h>
  10.  
  11. static inline size_t newgap(size_t gap)
  12. {
  13.   gap = (gap*10)/13;
  14.   if ( gap == 9 || gap == 10 )
  15.     gap = 11;
  16.  
  17.   if ( gap < 1 )
  18.     gap = 1;
  19.   return gap;
  20. }
  21.  
  22. void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
  23. {
  24.   size_t gap = nmemb;
  25.   size_t i, j;
  26.   char *p1, *p2;
  27.   int swapped;
  28.  
  29.   do {
  30.     gap = newgap(gap);
  31.     swapped = 0;
  32.     
  33.     for ( i = 0, p1 = base ; i < nmemb-gap ; i++, p1 += size ) {
  34.       j = i+gap;
  35.       if ( compar(p1, p2 = (char *)base+j*size) > 0 ) {
  36.     memswap(p1, p2, size);
  37.     swapped = 1;
  38.       }
  39.     }
  40.   } while ( gap > 1 || swapped );
  41. }
  42.  
  43.